#pragma once


enum Color{RED, BLACK};

template<class T>
struct RBTreeNode
{
	RBTreeNode<T>* _left;
	RBTreeNode<T>* _right;
	RBTreeNode<T>* _parent;
	Color _color;
	T _value;

	RBTreeNode(const T& value = T(), Color color = RED)
		: _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _color(color)
		, _value(value)
	{}
};


template<class T, class Ref, class Ptr>
struct RBTreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef RBTreeIterator<T, Ref, Ptr> Self;

	RBTreeIterator(Node* pNode = nullptr)
		: _pNode(pNode)
	{}

	// 具有指针类似的操作
	Ref operator*()
	{
		return _pNode->_value;
	}

	Ptr operator->()
	{
		return &(operator*());
	}

	//  可以移动
	Self& operator++()
	{
		Increament();
		return *this;
	}

	Self operator++(int)
	{
		Self temp(*this);
		Increament();
		return temp;
	}

	Self& operator--()
	{
		Decreament();
		return *this;
	}

	Self operator--(int)
	{
		Self temp(*this);
		Decreament();
		return temp;
	}

	bool operator==(const Self& s)const
	{
		return _pNode == s._pNode;
	}

	bool operator!=(const Self& s)const
	{
		return _pNode != s._pNode;
	}

	// 
	void Increament()
	{
		if (_pNode->_right)
		{
			// 到右子树中找最左侧的节点
			_pNode = _pNode->_right;
			while (_pNode->_left)
			{
				_pNode = _pNode->_left;
			}
		}
		else
		{
			Node* parent = _pNode->_parent;
			while (_pNode == parent->_right)
			{
				_pNode = parent;
				parent = _pNode->_parent;
			}
			
			// 注意：特殊情况-->根节点没有右子树的场景
			if (_pNode->_right != parent)
			{
				_pNode = parent;
			}
		}
	}

	void Decreament()
	{
		if (_pNode->_parent->_parent == _pNode && RED == _pNode->_color)
		{
			// 迭代器在end位置
			// 对end进行渐渐---要拿到最右侧的节点
			_pNode = _pNode->_right;
		}
		else if (_pNode->_left)
		{
			_pNode = _pNode->_left;
			while (_pNode->_right)
			{
				_pNode = _pNode->_right;
			}
		}
		else
		{
			Node* parent = _pNode->_parent;
			while (_pNode == parent->_left)
			{
				_pNode = parent;
				parent = _pNode->_parent;
			}

			_pNode = parent;
		}
	}

	Node* _pNode;
};

// 约定：红黑树实现时不考虑key重复的情况
template<class T, class KeyOfValue>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:
	typedef RBTreeIterator<T, T&, T*> iterator;
public:
	RBTree()
		: _head(new Node())
		, _size(0)
	{
		_head->_left = _head;
		_head->_right = _head;
		_head->_parent = nullptr;
	}

	~RBTree()
	{
		Destroy(GetRoot());
		delete _head;
		_head = nullptr;
		_size = 0;
	}

	/////////////////////////////////////////////
	// 迭代器
	iterator Begin()
	{
		return iterator(_head->_left);
	}

	iterator End()
	{
		return iterator(_head);
	}

	pair<iterator, bool> Insert(const T& value)
	{
		// 1. 按照二叉搜索树的规则插入新节点
		// 空树
		Node*& root = GetRoot();
		Node* newNode = nullptr;
		if (nullptr == root)
		{
			root = new Node(value, BLACK);
			root->_parent = _head;
			newNode = root;
		}
		else
		{
			// 非空
			// 按照二叉搜索树的特性找待插入节点在树中的位置
			Node* cur = root;
			Node* parent = _head;
			KeyOfValue kofV;
			while (cur)
			{
				parent = cur;
				if (kofV(value) < kofV(cur->_value))
					cur = cur->_left;
				else if (kofV(value) > kofV(cur->_value))
					cur = cur->_right;
				else
					return make_pair(iterator(cur), false);
			}

			// 插入新节点
			cur = new Node(value);
			newNode = cur;
			if (kofV(value) < kofV(parent->_value))
				parent->_left = cur;
			else
				parent->_right = cur;

			cur->_parent = parent;

			// 2. 检测新节点插入之后是否违反性质三：即是否存在红色节点连在一起的情况
			//    因为新插入节点cur的颜色是红色的，如果cur双亲parent节点的颜色也是红色的
			//    则违反了性质三
			while (parent != _head && RED == parent->_color)   // ???
			{
				// 违反了性质三
				Node* grandFather = parent->_parent;
				// 此处grandFather一定不为空
				// 因为：parent是红色的，则parent一定不是根节点，parent的双亲一定是存在的
				if (parent == grandFather->_left)
				{
					// 课件中给的三种情况
					Node* uncle = grandFather->_right;
					if (uncle && RED == uncle->_color)
					{
						// 情况一：叔叔节点存在且为红
						parent->_color = BLACK;
						uncle->_color = BLACK;
						grandFather->_color = RED;
						cur = grandFather;
						parent = cur->_parent;
					}
					else
					{
						// 叔叔节点为空 || 叔叔节点存在且为黑--->即情况二 或者 情况三
						// 情况三
						if (cur == parent->_right)
						{
							// 先对parent进行左单旋，然后将parent和cur交换---->变成情况二
							RotateLeft(parent);
							swap(parent, cur);
						}

						// 情况二：
						// 将祖父和双亲节点的颜色交换，然后再对祖父树进行右单旋
						grandFather->_color = RED;
						parent->_color = BLACK;
						RotateRight(grandFather);
					}
				}
				else
				{
					// 课件总给的三种情况的反情况
					// parent现在是双亲的右孩子
					Node* uncle = grandFather->_left;
					if (uncle && RED == uncle->_color)
					{
						// 情况一的反情况
						parent->_color = BLACK;
						uncle->_color = BLACK;
						grandFather->_color = RED;
						cur = grandFather;
						parent = cur->_parent;
					}
					else
					{
						// 叔叔节点不存在 || 叔叔节点存在并且颜色是黑色
						if (cur == parent->_left)
						{
							// 情况三的反情况：
							RotateRight(parent);
							swap(cur, parent);
						}

						// 情况二的反情况：
						parent->_color = BLACK;
						grandFather->_color = RED;
						RotateLeft(grandFather);
					}
				}
			}
		}

		// 需要更新_head的left和right指针域
		_head->_left = MostLeft();
		_head->_right = MostRight();
		root->_color = BLACK;
		++_size;
		return make_pair(iterator(newNode), true);
	}

	size_t Size()const
	{
		return _size;
	}

	bool Empty()const
	{
		return 0 == _size;
	}

	void Swap(RBTree<T, KeyOfValue>& t)
	{
		std::swap(_head, t._head);
	}

	void Clear()
	{
		Destroy(GetRoot());
		_size = 0;
	}

	void InOrder()
	{
		cout << "中序遍历: ";
		InOrder(GetRoot());
		cout << endl;
	}

	bool IsValidRBTree()
	{
		Node* root = GetRoot();
		if (nullptr == root)
			return true;

		// 检测是否违反性质2
		if (RED == root->_color)
		{
			cout << "违反了性质二：根节点必须为黑色" << endl;
			return false;
		}

		// 求一条路径中黑色节点的个数--比如：最左侧路径中黑色节点个数
		size_t blackCount = 0;
		Node* cur = root;
		while (cur)
		{
			if (BLACK == cur->_color)
				blackCount++;

			cur = cur->_left;
		}

		size_t pathBlackCount = 0;
		return IsValidRBTree(root, blackCount, pathBlackCount);
	}

	iterator Find(const T& value)
	{
		Node* cur = GetRoot();
		KeyOfValue kofV;
		while (cur)
		{
			if (kofV(value) == kofV(cur->_value))
				return iterator(cur);
			else if (kofV(value) < kofV(cur->_value))
				cur = cur->_left;
			else
				cur = cur->_right;
		}

		return End();
	}
private:
	bool IsValidRBTree(Node* root, const size_t blackCount, size_t pathBlackCount)
	{
		if (nullptr == root)
			return true;

		// 统计黑色单条路径中黑色节点的个数
		if (BLACK == root->_color)
			pathBlackCount++;

		// 检测性质3
		Node* parent = root->_parent;
		if (_head != parent && 
			RED == root->_color && RED == parent->_color)
		{
			cout << "违反了性质3：不能有连在一起的红色节点" << endl;
			return false;
		}

		if (nullptr == root->_left && nullptr == root->_right)
		{
			// 已经来到了某条路径的末尾
			if (pathBlackCount != blackCount)
			{
				cout << "违反了性质4：每条路径中黑色节点个数要相同" << endl;
				cout << blackCount << "---" << pathBlackCount << endl;
				return false;
			}
		}

		return IsValidRBTree(root->_left, blackCount, pathBlackCount) &&
			   IsValidRBTree(root->_right, blackCount, pathBlackCount);
	}

	void InOrder(Node* root)
	{
		if (root)
		{
			InOrder(root->_left);
			cout << root->_value << " ";
			InOrder(root->_right);
		}
	}

	void Destroy(Node* &root)
	{
		if (root)
		{
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
			root = nullptr;
		}
	}

	void RotateLeft(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		// 右单支
		if (subRL)
			subRL->_parent = parent;

		subR->_left = parent;

		// 更新parent和subR的双亲
		Node* pparent = parent->_parent;
		parent->_parent = subR;
		subR->_parent = pparent;

		// 还需要处理pparent的孩子
		if (pparent == _head)
			_head->_parent = subR;
		else
		{
			if (parent == pparent->_left)
				pparent->_left = subR;
			else
				pparent->_right = subR;
		}
	}

	void RotateRight(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		// 左单支
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;

		// 更新parent和subL的双薪
		Node* pparent = parent->_parent;
		parent->_parent = subL;
		subL->_parent = pparent;

		if (pparent == _head)
			_head->_parent = subL;
		else
		{
			if (parent == pparent->_left)
				pparent->_left = subL;
			else
				pparent->_right = subL;
		}
	}

	Node*& GetRoot()
	{
		return _head->_parent;
	}

	Node* MostLeft()
	{
		Node* cur = GetRoot();
		if (nullptr == cur)
			return _head;

		while (cur->_left)
		{
			cur = cur->_left;
		}

		return cur;
	}

	Node* MostRight()
	{
		Node* cur = GetRoot();
		if (nullptr == cur)
			return _head;

		while (cur->_right)
		{
			cur = cur->_right;
		}

		return cur;
	}
private:
	Node* _head;
	size_t _size;
};


#if 1
struct KeyOfValue
{
	const int& operator()(const int& value)
	{
		return value;
	}
};

void TestRBTree()
{
	int a[] = { 5, 3, 4, 1, 7, 8, 2, 6, 0, 9 };
	RBTree<int, KeyOfValue> t;
	for (auto e : a)
		t.Insert(e);

	t.InOrder();
	if (t.IsValidRBTree())
	{
		cout << "t is valid RBTree!!!" << endl;
	}
	else
	{
		cout << "t is invalid RBTree!!!" << endl;
	}


	auto it = t.Begin();
	while (it != t.End())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	it = t.End();
	while (it != t.Begin())
	{
		--it;
		cout << *it << " ";
	}
	cout << endl;
}
#endif